#leetcode题目1143：最长公共子序列
#难度：中等
#时间复杂度：O(n^2)
#空间复杂度：O(n^2)
#方法：多维动态规划

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        """
        最长公共子序列
        给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
        如果不存在公共子序列，返回 0。
        """
        l1 = len(text1)
        l2 = len(text2)
        
        # 初始化记忆化数组，-1表示未计算
        dp = [[-1] * l2 for _ in range(l1)]
        
        return self.process(text1, text2, 0, 0, dp)

    def process(self, text1: str, text2: str, index1: int, index2: int, dp: list) -> int:
        """
        递归处理函数 - 记忆化搜索
        :param text1: 第一个字符串
        :param text2: 第二个字符串
        :param index1: 第一个字符串的当前索引
        :param index2: 第二个字符串的当前索引
        :param dp: 记忆化数组
        :return: 最长公共子序列的长度
        """
        l1 = len(text1)
        l2 = len(text2)
        
        # 基础情况：任一字符串到达末尾
        if index1 == l1 or index2 == l2:
            return 0
        
        # 记忆化检查：如果已经计算过，直接返回
        if dp[index1][index2] != -1:
            return dp[index1][index2]
        
        res = 0
        
        # 如果当前字符相同，可以加入公共子序列
        if text1[index1] == text2[index2]:
            res = self.process(text1, text2, index1 + 1, index2 + 1, dp) + 1
        else:
            # 如果当前字符不同，有两种选择：
            # 1. 跳过text1的当前字符
            # 2. 跳过text2的当前字符
            # 取两者的最大值
            p2 = self.process(text1, text2, index1, index2 + 1, dp)
            p3 = self.process(text1, text2, index1 + 1, index2, dp)
            res = max(p2, p3)
        
        # 存储结果到记忆化数组
        dp[index1][index2] = res
        return res

#测试数据
text1 = "abcde"
text2 = "ace"
#预期输出：3,最长公共子序列是"ace"
solution = Solution()
print(solution.longestCommonSubsequence(text1, text2))


text1 = "abc"
text2 = "abc"
#预期输出：3,最长公共子序列是"abc"
solution = Solution()
print(solution.longestCommonSubsequence(text1, text2))

text1 = "abc"
text2 = "def"
#预期输出：0,最长公共子序列是"",没有公共子序列
solution = Solution()
print(solution.longestCommonSubsequence(text1, text2))




